package baseclass.a_sort.bucketSort;


import baseclass.a_sort.ArraysTool;

/**
 * @date 2020/2/26 23:37
 */
public class Demo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 6, 7};
        System.out.println(getMaxNeighbor(arr));
    }

    public static int getMaxNeighbor(int[] arr) {
        if (!ArraysTool.check(arr)) return 0;
        int min = 0;
        int max = 0;
        for (int e : arr) {
            max = Math.max(max, e);
            min = Math.min(min, e);
        }
        //把arr元素按照一定范围分到桶中，至少有一个空桶.
        // 桶要记录最大值和最小值，这是我们关心的
        //第一个桶和最后一个桶必然非空，看桶的范围选择
        int[] maxs = new int[arr.length + 1];
        int[] mins = new int[arr.length + 1];
        //当前桶是否空,默认是false
        boolean[] hasEle = new boolean[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            int index = getIndex(arr, i, max, min);
            if (!hasEle[index]) {
                maxs[index] = mins[index] = arr[i];
                hasEle[index] = true;
            } else {
                maxs[index] = Math.max(maxs[index], arr[i]);
                mins[index] = Math.min(mins[index], arr[i]);
            }
        }
        //遍历桶，不一定最大值出现在空桶的前后
        int res = 0;
        //第一个桶非空
        int lastMax = maxs[0];
        for (int i = 1; i < hasEle.length - 1; i++) {
            if (hasEle[i]) {
                //当前桶的min - 上一个非空桶的max
                res = Math.max(res, mins[i] - lastMax);
                lastMax = maxs[i];
            }
        }
        return res;
    }


    /**
     *
     * 譬如arr长5，也就是有5个元素。那么桶的大小为6.最大索引是5.
     * max必定属于最后一个桶，min必定属于第1个桶，即0号
     */
    public static int getIndex(int[] arr, int i, int max, int min) {
        return (arr[i] - min) * arr.length / (max - min);
    }
}
